﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Bioinformatics.Algorithms
{
    public static class SequenceAligner
    {
        public static void AlignPair(string sequenceA, string sequenceB, float[,] similarityMatrx, int penalty, int match)
        {
            //create lcs matrix
            var lcsMatrix = new float[sequenceA.Length + 1,sequenceB.Length + 1];
            
            //create direction matrix
            var directionMatrix = new int[sequenceA.Length + 1,sequenceB.Length + 1];

            //keep track of largest value in the matrix
            var maxI = 1;
            var maxJ = 1;

            //populate matrices
            for(var i = 1; i <= sequenceA.Length; i++)
                for(var j = 1; j <= sequenceB.Length; j++)
                {
                    var diagonal = lcsMatrix[i, j] + similarityMatrx[0, 0];
                    var left = lcsMatrix[i - 1, j] - penalty;
                    var down = lcsMatrix[i, j - 1] - penalty;

                    if (diagonal > left && diagonal > down && diagonal > 0)
                    {
                        lcsMatrix[i, j] = diagonal;
                        directionMatrix[i, j] = 0;
                    }
                    else if (left > diagonal && left > down && left > 0)
                    {
                        lcsMatrix[i, j] = left;
                        directionMatrix[i, j] = 1;
                    }
                    else if (down > diagonal && down > left && down > 0)
                    {
                        lcsMatrix[i, j] = down;
                        directionMatrix[i, j] = -1;
                    }
                    else
                    {
                        lcsMatrix[i, j] = 0;
                        directionMatrix[i, j] = int.MaxValue;
                    }
                    if (lcsMatrix[i, j] > lcsMatrix[maxI, maxJ])
                    {
                        maxI = i;
                        maxJ = j;
                    }
                }
            
            var alignedSequenceA = new StringBuilder();
            var alignedSequenceB = new StringBuilder();

            while(maxI != 0 && maxJ != 0)
            {
                if(directionMatrix[maxI,maxJ] == int.MaxValue)
                {
                    break;    
                }
                else if(directionMatrix[maxI,maxJ] == 0)
                {
                    alignedSequenceA.Append(sequenceA[--maxI]);
                    alignedSequenceB.Append(sequenceB[--maxJ]);
                }
                else if(directionMatrix[maxI, maxJ] == 1)
                {
                    alignedSequenceA.Append(sequenceA[--maxI]);
                    alignedSequenceB.Append(sequenceB[--maxJ]);                    
                }
            }
        }

    }
}
